Packet Networks such as Internet Protocol (IP) networks or Ethernet networks typically operate on a “Best Efforts” basis. This means that they (or the network elements of which they are comprised) usually forward their data units or packets quickly across the network, but may occasionally experience congestion when they receive more packets than can be forwarded quickly. In this case they typically delay or drop excess packets, which may cause inconvenience to the senders or receivers of the packets.
Techniques have been developed to provide a more discriminating forwarding behaviour by, for example, giving some packets priority, or higher priority than others, based for example on which of a number of different traffic classes they are identified as belonging to, or on their source or intended destination. Such techniques typically need to be complemented by mechanisms such as Admission Control mechanisms which may be used to control the rate at which the high (or higher) priority packets enter the network, in order to prevent them from being able to congest or monopolise the resources of the network to the extent that they completely exclude packets having lower priority from the network. By appropriate use of such mechanisms and appropriate configuration, the resources available to the network may effectively be partitioned in such a way as to ensure that the network will not accept higher priority packets at a higher rate than the rate at which the network can actually guarantee to provide such packets with priority treatment, while also ensuring that packets having lower priority cannot be completely excluded.
Other schemes for controlling congestion rely on the network (or the network elements therein) providing a signal to the senders or receivers of packets (or other types of data units) when congestion is experienced allowing them to “back-off” (i.e. to reduce the rate at which data units are being sent) in response thereto, and thereby alleviate the congestion. Such schemes generally rely on sources taking responsibility for the rate at which they send data by implementing congestion control mechanisms, but it is generally in their interests to do so, because if sources persist in sending traffic through a congested network or via a congested network element router, it could become (more) seriously overloaded or congested, leading to (more) traffic being dropped and other network elements becoming congested as well. It is therefore generally in the interest of sources to monitor feedback signals that characterise path congestion in order to detect when a path their data is following is getting congested, in which case they react by reducing their throughput. They may slowly increase their rate when there is no sign of the path becoming congested.
Typical path characterisation metrics that sources monitor are average roundtrip time (RTT) for the data path, variance of the roundtrip time (jitter) and level of congestion on the path.
The congestion level can be signalled either implicitly (through congested routers dropping packets when their buffers overflow or to protect themselves) or explicitly (through mechanisms such as explicit congestion notification—see later). Currently the most common option is implicit signalling.
Sources using Transmission Control Protocol (TCP) are able to detect losses, because a packet loss causes a gap in the sequence; whenever a TCP source detects a loss, it is meant to halve its data transmission rate, but no more than once per round trip time, which alleviates the congestion on the network element at the bottleneck.
Recent approaches to managing congestion in the Internet and other networks require network elements such as routers (or switches) in the network to perform Active Queue Management (AQM) and to signal congestion using some marking scheme. In such approaches, a router may choose a proportion of the packets being forwarded based on its current congestion level, and mark them with a congestion mark, typically using a protocol such as ECN (RFC 2481—A Proposal to add Explicit Congestion Notification (ECN) to IP). If the router is uncongested, then very few packets (or no packets) will be marked. If the router is congested many (or all) packets will be marked. As will become apparent, by network elements marking (rather than dropping) packets, thereby allowing senders to react to marks on forwarded packets (rather than detected packet drops), it becomes possible to avoid congestion reaching a level at which packet drops are necessary at all.
With reference to FIG. 1, an overview of a generalised network element 10, such as a router or switch, is shown. Flows of packets 12 arrive at the network element from other nodes in a network via one or more network interfaces 14, and are presented for onward transmission to other nodes in the network via another network interface 16. If the network element 10 is performing a packet marking process to indicate congestion, a packet-marking means 18 is present at the network element 10 or at one or more of its network interfaces 16.
Existing mechanisms for marking packets are typically based upon inspecting the real queue of packets at the router (or switch) interface and marking the packets if this queue is long (i.e. above a predetermined threshold). An example of such an approach is given in “Random Early Marking: An Optimization Approach to Internet Congestion Control” by David Lapsley and Steven Low (Proceedings of the 7th IEEE International Conference on Networks, 28 Sep.-1 Oct. 1999). Such techniques are not difficult to implement with current switches and routers, but they are not entirely satisfactory because they do not start to signal congestion until the real queue has started to grow in size. It is preferable generally to operate the network so that real queues very seldom grow in size since long queues mean increased latency and packet loss. Thus it would be better if the marking mechanism could start marking in the presence of imminent congestion before the real queue start to grow. This is the idea of virtual queue marking.
Random Early Marking, also called Random Early Detection (RED), randomly drops/marks packets with a probability “p” that depends upon the smoothed queue “qave”. In a RED-based AQM, a smoothed queue qave is continuously estimated by means of an exponentially-weighted moving average (EWMA) of the real queue “q”:qave←(1−wq)qave+wqq where “wq” is the weight given to the real queue's length. Many algorithms have been proposed for how to relate the smoothed queue qave to the probability of marking (or dropping) a packet. For example, in the algorithm known as the “Gentle” variant of RED, when the smoothed queue size gave is below a minimum threshold “q0” then no packets are dropped/marked. When qave is between “q0” and “q1” then packets are discarded with a probability p, between 0 and p1, which is linearly proportional to qave. When qave is greater than threshold q1 then probabilistic dropping/marking continues with an increased probability ranging between p1 and pmax, which still depends linearly on gave.
One significant practical problem with RED is that it is very sensitive to the setting of the parameters.
Because RED uses a smoothed queue, a sudden burst of packets can still lead to many packets being in the real queue—and hence significant delays to packets—before the smoothed queue increases enough for RED to start (randomly) dropping or marking packets (and thereby signal to senders to “back-off”).
RED is widely used in today's Internet because it allows sources to react more promptly to incipient congestion and it keeps queues from growing unnecessarily long. Equipment vendors have implemented variants of RED, e.g. Cisco's proprietary implementation is known as “Weighted Random Early Detection” (WRED).
Virtual Queue Marking
An example of such early marking has been standardised in the IETF PCN Working Group (http://www.ietf.org/html.charters/pcn-charter.html), where PCN refers to “Pre-Congestion Notification”. This working group has standardised two marking mechanisms based on looking at how the arrival rate of packets compares not to the line-rate (as the real queue does) but instead to a slightly reduced rate. These are specified in RFC 5670: “Metering and Marking Behaviour of PCN-Nodes” (P. Eardley, November 2009). This “virtual queue” experiences congestion before the real queue, and hence can provide more timely congestion signals. An academic discussion of the advantages of such a mechanism is given in “Resource pricing and the evolution of congestion control” by R. J. Gibbens and F. P. Kelly (Automatica 35, 1999). Virtual queues were first proposed in a different form (and for use in ATM networks) in “Buffer Overflow Asymptotics for a Switch Handling Many Traffic Sources” by Costas Courcoubetis and Richard Weber (Journal of Applied Probability 33, pages 886-903, 1996). The precise form discussed here was proposed by Kunniyur and Srikant in “Analysis and Design of an Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management” (Proc. ACM SIGCOMM'01, Computer Communication Review 31 (4), October 2001).
It will be noted that the term “virtual queue” is also used in switch and router hardware design to denote a virtual queue on an ingress interface that tracks the queue on an egress interface, but this has no relation to the virtual queue discussed here.
Virtual Queue Marking (VQM) defines a strategy—to be implemented on network interfaces—to mark packets of a packet-switched network with a signal expressing the state of congestion of that interface. This packet marking strategy is based on a congestion measurement defined by a virtual queue. A virtual queue is a conceptual queue that is actually simply a single variable recording the length of the virtual queue, where the lengths (i.e. sizes) of packets are added to it as they arrive while some fraction of the actual line-rate of that interface is subtracted at the same time. This means that an interface's virtual queue builds up more rapidly than its real queue. Typically the marking algorithm is based on the instantaneous length of the virtual queue, rather than its smoothed value. Therefore most of the time the real queue is essentially empty—at most a couple of packets—so there are no buffering or re-transmission delays, and the end-to-end latency can approach the underlying ‘speed of light’ transmission time. However, there is still plenty of buffer available to absorb a temporary burst of traffic (for instance during TCP's start-up phase). No packets need ever be dropped (if marking is used as the signalling technique, rather than dropping).
Another advantage of the virtual queue compared with RED is that the marking algorithm can be simplified. For example, in “Performance Evaluation of Pre-Congestion Notification” by X. Zhang and A. Charny (International Workshop on Quality of Service (IWQoS), Enschede, The Netherlands, June 2008) showed using simulations that a simple ‘step’ marking algorithm can be used. In this, no packets are marked/dropped if the length of the virtual queue is less than a threshold, and all are marked/dropped if it is above. The paper also shows that the results are fairly insensitive to the exact parameter value.
It is of course possible to operate a virtual queue based on its smoothed virtual queue (VQ) length and for the algorithm to be more complex than a simple step function (for example a probabilistic scheme akin to Gentle RED).
Virtual queues have been implemented by several vendors, for example Broadcom in their Triumph and Scorpion switches and Cisco in their Nexus 5xxx and 7xxx range of switches. Broadcom chips are also used by most vendors of mid-range switches.
FIG. 2 shows a model illustrating a Virtual Queue Marking (VQM) process. As each new packet arrives and is added to the real queue, the size of the virtual queue is incremented by the number of bytes in the new packet (or by a unit amount, which may be applicable in cases where packets are equal or similar in size, or where it is appropriate to treat them as such). If packets are able to be presented for onward transmission to other nodes in the network at an “actual line-rate” of X bytes per second (bps), the virtual queue is decremented at a “virtual drain-rate” of θX bps, where 8<1. (Typically, 8 is close to but slightly less than 1, e.g. 0.98.).
The size of the virtual queue (rather than of the actual queue) is then used to decide whether or not to send a congestion signal (i.e. a signal expressing a state of congestion for that interface). Typically a congestion signal would be sent if the size of the virtual queue exceeds some threshold. There are several ways of coding a congestion signal; a desirable way is to ‘mark’ a packet, by setting a bit in the packet header to 1 if the signal is ‘congested interface’, or to 0 if the signal is ‘uncongested interface’. Another possible way of using the measurement of congestion that the virtual queue provides, rather than marking packets, is to send an alert to a management system. Alternatively (but less desirably in most circumstances), the traffic class of the real packet may be re-marked, or the real packet might be dropped or re-routed. Various other types of action or sanction, punitive or non-punitive, may be used.
Virtual queue work to date has been based on the assumption that the line-rate of X bytes per second is fixed and therefore the rate at which the virtual queue is decremented of θX is set at configuration time. However, there are in fact circumstances when the real line-rate will vary. Examples include a wireless interface changing its rate, or if the line is actually a virtual link such as a tunnel where the underlying path changes. In such circumstances, the present inventors have identified that it would be appropriate for the virtual queue rate to be altered to reflect the new line-rate, Xnew, i.e. setting it to θXnew. In addition to this, and as will be explained later, they have identified a further, separate adjustment that can also be made in such circumstances in order to improve the response so that any measure of congestion signalled (by marking, dropping or otherwise) more accurately reflects the near-term danger of packets (or other data units) being dropped by the real queue or otherwise failing to be forwarded as intended.
Referring to earlier patent applications of possible background relevance to techniques that use “counters” and “counts” (albeit not in relation to “virtual queue” techniques), US2007/230493 (“Dravida et al”) relates generally to wireless communications, and more particularly to a memory management technique for high speed media access control.